The present invention relates to memory management. More specifically, the invention relates to automatic reclamation of memory occupied by program segments that are no longer active, commonly referred to as garbage collection.
The execution or running of a computer program causes certain areas of memory to be assigned values. For example, whenever a variable is declared, a certain area of memory having a certain address is set aside to store the value associated with that variable. It is difficult to predict how much memory an application program will require (conditions can vary each time the application is run). Thus, computing environments are designed with tools to handle the changing memory requirements of application programs.
In general, application memory management combines two related tasks: allocation and recycling. Allocation occurs when the program requests a block of memory (e.g., when a variable is declared or an object is created). When a request is made, the memory manager must allocate that block of memory out of the larger block of memory it has received from the operating system. The tool that performs this task is known as the “allocator.” Recycling involves reusing memory blocks that contain data that is no longer required by the program. There are two approaches to recycling memory: manual memory management, where the programmer decides when memory can be reused, and automatic memory management, where a software routine reclaims memory on its own.
The basic problem in managing memory is knowing when to keep the data stored in the memory and when to throw it away, so that the memory can be reused. Conceptually, proper memory management should be easy. However, it is difficult to achieve in practice. Furthermore, poor memory management can affect the robustness and speed of programs.
Programming languages designed with automatic memory management use specialized routines (typically called “garbage collectors”) that search the memory used by a program for program segments (e.g., objects, methods, etc.) that are no longer active. Upon finding an inactive segment the routine reclaims the memory for re-use. A common garbage collection technique involves following references to determine which blocks of memory are reachable from program variables. Automatic memory managers that use this technique are called “tracing collectors.” Tracing collectors often implement a mark-and-sweep strategy. First, the collector examines the program variables or, more broadly, objects and determines all blocks of memory that are referred to by those objects. These blocks are added to a list of blocks that will be further examined. For each block on the list, the collector sets a flag on the block (or marks the block) to show that it is still required and that it has been examined. The collector also adds any blocks pointed to by the block being examined that have not been marked to the list of blocks to be examined. The collector then sweeps the allocated memory and returns any blocks that have not been marked to the allocator for reuse.
Mark-and-sweep garbage collection can be implemented using a three-color marking system. Initially all objects are assumed live and colored white. Every object that can be reached during the tracing process is marked gray. Then the gray objects are processed in an iterative fashion. While there are still gray objects, one of the gray objects is chosen, it is colored black, and then all of the objects that can be reached from that gray object, if they are not already gray or black, are colored gray. Another gray object is chosen and the process is continued until there are no more gray objects. When the process is complete, all live objects are colored black, and all other objects are white.